package com.shm.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * 131. 分割回文串
 * 给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
 *
 * 回文串 是正着读和反着读都一样的字符串。
 *
 *
 *
 * 示例 1：
 *
 * 输入：s = "aab"
 * 输出：[["a","a","b"],["aa","b"]]
 * 示例 2：
 *
 * 输入：s = "a"
 * 输出：[["a"]]
 *
 *
 * 提示：
 *
 * 1 <= s.length <= 16
 * s 仅由小写英文字母组成
 * @author SHM
 */
public class PartitionSS {
    /**
     * 动态规划 + 回溯算法
     * 求所有的分割方案，凡是求所有方案的题基本上都没有什么优化方案，就是「爆搜」。
     *
     * 问题在于，爆搜什么？显然我们可以爆搜每个回文串的起点。如果有连续的一段是回文串，我们再对剩下连续的一段继续爆搜。
     *
     * 为什么能够直接接着剩下一段继续爆搜？
     *
     * 因为任意的子串最终必然能够分割成若干的回文串（最坏的情况下，每个回文串都是一个字母）。
     *
     * 所以我们每次往下爆搜时，只需要保证自身连续一段是回文串即可。
     *
     * 举个🌰 来感受下我们的爆搜过程，假设有样例 abababa，刚开始我们从起点第一个 a 进行爆搜：
     *
     * 发现 a 是回文串，先将 a 分割出来，再对剩下的 bababa 进行爆搜
     * 发现 aba 是回文串，先将 aba 分割出来，再对剩下的 baba 进行爆搜
     * 发现 abab 是回文串，先将 abab 分割出来，再对剩下的 aba 进行爆搜
     * 发现 ababab 是回文串，先将 ababab 分割出来，再对剩下的 a 进行爆搜
     * ...
     *
     * 然后再对下一个起点（下个字符） b 进行爆搜？
     *
     * 不需要。
     *
     * 因为单个字符本身构成了回文串，所以以 b 为起点，b 之前构成回文串的方案，必然覆盖在我们以第一个字符为起点所展开的爆搜方案内（在这里就是对应了上述的第一步所展开的爆搜方案中）。
     *
     * 因此我们只需要以首个字符为起点，枚举以其开头所有的回文串方案，加入集合，然后对剩下的字符串部分继续爆搜。就能做到以任意字符作为回文串起点进行分割的效果了。
     *
     * 一定要好好理解上面那句话 ~
     *
     * 剩下的问题是，我们如何快速判断连续一段 [i, j] 是否为回文串，因为爆搜的过程每个位置都可以作为分割点，复杂度为 O(2^n)O(2
     * n
     *  ) 的。
     *
     * 因此我们不可能每次都使用双指针去线性扫描一遍 [i, j] 判断是否回文。
     *
     * 一个直观的做法是，我们先预处理除所有的 f[i][j]，f[i][j] 代表 [i, j] 这一段是否为回文串。
     *
     * 预处理 f[i][j] 的过程可以用递推去做。
     *
     * 要想 f[i][j] == true ，必须满足以下两个条件：
     *
     * f[i + 1][j - 1] == true
     * s[i] == s[j]
     * 由于状态 f[i][j] 依赖于状态 f[i + 1][j - 1]，因此需要我们左端点 i 是从大到小进行遍历；而右端点 j 是从小到大进行遍历。
     *
     * 因此，我们的遍历过程可以整理为：右端点 j 一直往右移动（从小到大），在 j 固定情况下，左端点 i 在 j 在左边开始，一直往左移动（从大到小）
     *
     * 时间复杂度：动态规划预处理的复杂度为 O(n^2)O(n
     * 2
     *  )；爆搜过程中每个字符都可以作为分割点，并且有分割与不分割两种选择，方案数量为 2^{n - 1}2
     * n−1
     *  ，每个字符都需要往后检查剩余字符的分割情况，复杂度为 O(n)O(n)。整体复杂度为 O(n * 2^n)O(n∗2
     * n
     *  )
     * 空间复杂度：动态规划部分的复杂度为 O(n^2)O(n
     * 2
     *  )；方案数量最多为 2^{n - 1}2
     * n−1
     *  ，每个方案都是完整字符串 s 的分割，复杂度为 O(n)O(n)，整体复杂度为 O(n * 2^n)O(n∗2
     * n
     *  )
     * 总结
     * 对于此类要枚举所有方案的题目，我们都应该先想到「回溯算法」。
     *
     * 「回溯算法」从算法定义上来说，不一定要用 DFS 实现，但通常结合 DFS 来做，难度是最低的。
     *
     * 「回溯算法」根据当前决策有多少种选择，对应了两套模板。
     *
     * 每一次独立的决策只对应 选择 和 不选 两种情况：
     *
     * 确定结束回溯过程的 base case
     *
     * 遍历每个位置，对每个位置进行决策（做选择 -> 递归 -> 撤销选择）
     *
     *
     * void dfs(当前位置, 路径(当前结果), 结果集) {
     *     if (当前位置 == 结束位置) {
     *         结果集.add(路径);
     *         return;
     *     }
     *
     *     选择当前位置;
     *     dfs(下一位置, 路径(当前结果), 结果集);
     *     撤销选择当前位置;
     *     dfs(下一位置, 路径(当前结果), 结果集);
     * }
     * 每一次独立的决策都对应了多种选择（通常对应了每次决策能选择什么，或者每次决策能选择多少个 ...）:
     *
     * 确定结束回溯过程的 base case
     *
     * 遍历所有的「选择」
     *
     * 对选择进行决策 (做选择 -> 递归 -> 撤销选择)
     *
     *
     * void dfs(选择列表, 路径(当前结果), 结果集) {
     *     if (满足结束条件) {
     *         结果集.add(路径);
     *         return;
     *     }
     *
     *     for (选择 in 选择列表) {
     *         做选择;
     *         dfs(路径’, 选择列表, 结果集);
     *         撤销选择;
     *     }
     * }
     *
     * 作者：AC_OIer
     * 链接：https://leetcode-cn.com/problems/palindrome-partitioning/solution/wei-sha-yao-zhe-yang-bao-sou-ya-shi-ru-h-41gf/
     * @param s
     * @return
     */
    public List<List<String>> partition(String s) {
        int n = s.length();
        char[] cs = s.toCharArray();

        boolean[][] st= new boolean[n][n];
        for(int j=0;j<n;j++){
            for(int i=j;i>=0;i--){
                if(i==j){
                    st[i][j]=true;
                }else if(j-i+1==2){
                    st[i][j]=cs[i]==cs[j];
                }else{
                    st[i][j] = cs[i]==cs[j]&&st[i+1][j-1];
                }
            }
        }

        List<List<String>> ans = new ArrayList<>();
        List<String> cur = new ArrayList<>();
        dfs(s,ans,0,cur,st);
        return ans;
    }

    void dfs(String s,List<List<String>> ans,int index,List<String> cur,boolean[][] st){
        int n = s.length();
        if (index==n){
            ans.add(new ArrayList<>(cur));
        }
        for(int i=index;i<n;i++){
            if (st[index][i]){
                cur.add(s.substring(index,i+1));
                dfs(s,ans,i+1,cur,st);
                cur.remove(cur.size()-1);
            }
        }
    }
}
